Every computer and communication network which transfers data packets must implement some form of scheduling to insure that data traffic progresses through the network at a particular rate. At any given moment, a network may have hundreds of thousands or even millions of connections containing data queues waiting for transport through the network. Some form of scheduling is required to enable network elements to process these data queues in a fair and timely manner.
Typically, schedulers interact with the data queues to schedule the transmission of data through the network. Schedulers can be hierarchical in that the selected child also could be a scheduler which must choose from its children. The scheduler determines the order of data transmission from eligible data queues or other eligible child schedulers having data available. Generally, a separate process enqueues the data to a queue, but the separate process is coupled to scheduling in the way it announces the data availability or child eligibility. Schedulers periodically, or on request, choose a child with available data from which to transmit the data. The hierarchical scheduler establishes a transmission of data from the selected queue.
FIG. 1 illustrates a prior art data system 10 that includes a scheduling process 12 wherein the data path includes a series of data queues 14a, 14b, 14c, 14d and 14e (collectively referenced as data queue 14) and multiplexers 16a, 16b (collectively referenced as multiplexer 16). Although shown in FIG. 1 as a physical unit, in a typical scalable implementation, the multiplexers do not physically exist, but are implied by the scheduler's choice of data queue 14 for transmission. The scheduling process 12 may select from any of the data queues 14 having data available (“DA”); however, due to hierarchical nature of the implementation, the scheduling process 12 must request a child scheduler 18 to select from data queue 14d and data queue 14e. The child scheduler 18 then selects the appropriate data queue 14d, 14e. In this example, the scheduling process 12 may select data queues 14a, 14b and 14c directly.
One prior art weighted fair queuing process is disclosed in U.S. Pat. No. 7,373,420, issued to Lyon (hereinafter “the '420 patent”), the entire contents of which are herein incorporated by reference. FIG. 2 illustrates the weighted fair queuing process of the '420 patent, which includes an inverse credit management system that uses the assigned weights for each data queue to determine which queue to credit. Basically, the weighted fair queuing with inverse credit management (“WFQ-ICM”) scheduler 20 includes two complimentary processes: a WFQ credit distributor 22 and a transmit selector 24. The transmit selector 24 typically operates in a round-robin fashion, wherein each child with data available and positive credit takes a turn at transmitting data.
The credit process 22 grants credits to children whose current credits are less than the amount of data available (“ADA”) for that child. The amount of credits each child has accrued at any given time is tracked in a child credit state database 26. The amount of credits per child never exceeds that child's ADA. If at any time, a child has less credit than its ADA, it is included in the credit distributor 22 where it competes for more credit.
The transmit selector 24 selects children with positive credit counts to transmit data. When a child transmits data, credits are decremented from its current credit amount in the child credit state database 26 and returned to the credit distributor 22 for redistribution to other children having ADA greater than number of credits. The credit distributor 22 gives credits at the same rate as children spend credits (i.e., there is no outstanding balance), thus a key requirement of the WFQ-ICM scheduler 20 is that the system needs to know exactly how much data is available for transmission from each child at all times. This requirement prevents a child from deeming itself ineligible when it still has data available, rendering implementation of overlaying processes to determine eligibility based on rate practically impossible. Fundamentally, rate limits can force a child with data to stop transmitting or have no data available to the parent scheduler. This limitation also carries a heavy burden on hierarchical schedulers where ADA includes all descendant queues, no matter how many levels of hierarchy are involved—effectively coupling scheduling processes between scheduling levels.
Therefore, what is needed is a method, system and apparatus for weighted fair queuing with inverse credit management that may be used in the presence of rate-shaped traffic.